#!/usr/bin/python
#
# exp.py - Classes to represent underlying data structures for the grammar
#	 below, for the mini-compiler.
#
# Kurt Schmidt
# 8/07
#
# DESCRIPTION:
#		Just a translation of the C++ implementation by Jeremy Johnson (see
#		programext.cpp)
#
# EDITOR: cols=80, tabstop=2
#
# NOTES
#	environment:
#		a dict
#
#		Procedure calls get their own environment, can not modify enclosing env
#
#	Grammar:
#		program: stmt_list 
#		stmt_list:  stmt ';' stmt_list 
#		    |   stmt  
#		stmt:  assign_stmt 
#		    |  if_stmt 
#		    |  while_stmt 
#		assign_stmt: IDENT ASSIGNOP expr
#		define_stmt: DEFINE IDENT PROC '(' param_list ')' stmt_list END
#		if_stmt: IF expr THEN stmt_list ELSE stmt_list FI
#		while_stmt: WHILE expr DO stmt_list OD
#		expr: expr '+' term   
#		    | expr '-' term   
#		    | term            
#		term: term '*' factor   
#		    | factor            
#		factor:     '(' expr ')'  
#		    |       NUMBER 
#		    |       IDENT 
#

import sys

####  CONSTANTS   ################

	# the variable name used to store a proc's return value
returnSymbol = 'return'

tabstop = '  ' # 2 spaces

######   CLASSES   ##################

class TableEntry:
	'''For storing values in the tables'''
	def __init__(self, string, value):
		self.string = string
		self.value = value


class Instruction :
	'''Class for the RAM instructions'''

	def __init__ (self, func, operand, lineNum, varType):
		#func will be a string the function we call i.e. JMP or LD
		self.func = func
		#The argument if any
		self.operand = operand
		#Its line number
		self.lineNum = lineNum
		#type of variable used
		self.varType = varType
		#idea- field to set linked operand
		self.linkedoperand = ""
		self.linkedfunc = ""
class RAMInfo:
	'''Hold all info related to creating RAM programs'''
	def __init__(self):
		#instrList is the list or Instructions
		self.instrList = []
		#the counters are used for when we need to retrieve the next const, label, or temp
		self.constCount = 1
		self.labelCount = 1
		self.tempCount = 1
		self.lineCount = 1
		#the tables hold their respective variable
		self.constTable = []
		self.constValueTable = [] 
		self.localTable = []
		self.tempTable = []
		self.labelTable = []	
	def getNextTemp(self):
		result = "T" + str(self.tempCount)
		self.tempCount = self.tempCount +1
		return result

	def getNextLabel(self):
		result = "L" + str(self.labelCount)
		self.labelCount = self.labelCount + 1
		return result
	
	def getNextConst(self, value):
		isFound = 0
		for i in range(0,len(self.constValueTable)):
			if(self.constValueTable[i].value == value):
				isFound = 1
				return self.constValueTable[i].string
		if isFound == 0:
			result = "C" + str(self.constCount)
			self.constValueTable.append(TableEntry(result, value))
			self.constCount = self.constCount + 1
			return result

	def addInstr(self, func, operand, type):
		instr = Instruction(func, operand, self.lineCount, type)
		self.instrList.append(instr)
		self.lineCount = self.lineCount + 1

	def addLabel(self, lbl):
		instr = Instruction("LBL", lbl, self.lineCount, "LABEL")
		print "LineCount = "+ str(self.lineCount)
		self.instrList.append(instr)

	def instrDump(self, tail=""):
		programFile = open('program' + tail + '.ral','w')
		for p in range(0, len(self.instrList)):
			if(self.instrList[p].func != "NULL"): 
				programFile.write(self.instrList[p].func +" "+str(self.instrList[p].operand) +"\n")
				#print self.instrList[p].func +" "+str(self.instrList[p].operand)
		programFile.close()

	def memoryDump(self):
		memoryFile = open('memory.ral','w')
		for i in range(0, len(self.constTable)):
			value = -1
			for l in range(len(self.constValueTable)):
				if self.constValueTable[l].string == self.constTable[i].string:
					value = self.constValueTable[l].value
					break
			memoryFile.write(self.constTable[i].string[1:] + " "+ str(value) +"\n")
			#print self.constTable[i].string + "----->"+ str(self.constTable[i].value)
		for j in range(0, len(self.localTable)):
			memoryFile.write(str(self.localTable[j].value) + " 0 ;local value of " + self.localTable[j].string + "\n")
			#print self.localTable[j].string + "----->"+ str(self.localTable[j].value)
		for k in range(0, len(self.tempTable)):
			memoryFile.write(str(self.tempTable[k].value) + " 0 ;Temporary value " + self.tempTable[k].string + "\n")
			#print self.tempTable[k].string + "----->"+ str(self.tempTable[k].value)
		#for l in range(0, len(self.labelTable)):
			#print self.labelTable[l].string+ "----->"+ str(self.labelTable[l].value)
		memoryFile.close()

	def link(self):
		memCounter = 1;
		
		for p in range(0, len(self.instrList)):
			if(self.instrList[p].varType == "CONST"):
				isFound = 0
				for i in range(0, len(self.constTable)):
					if(self.constTable[i].string == self.instrList[p].operand):
						self.instrList[p].operand = self.constTable[i].value
						isFound = 1
				if isFound == 0:
					self.constTable.append(TableEntry(self.instrList[p].operand, memCounter))
					self.instrList[p].operand = memCounter
					if self.instrList[p].func == "LD":
						self.instrList[p].func = "LDA"
					if self.instrList[p].func == "ST":
						self.instrList[p].func = "STA"
					memCounter = memCounter + 1
		for p in range(0, len(self.instrList)):
			if(self.instrList[p].varType == "LOCAL"):
				isFound = 0
				for i in range( 0, len(self.localTable)):
					if(self.localTable[i].string == self.instrList[p].operand):
						self.instrList[p].operand = self.localTable[i].value
						isFound = 1
				if isFound == 0:
					self.localTable.append(TableEntry(self.instrList[p].operand, memCounter))	
					self.instrList[p].operand = memCounter
					if self.instrList[p].func == "LD":
						self.instrList[p].func = "LDA"
					if self.instrList[p].func == "ST":
						self.instrList[p].func = "STA"
					memCounter = memCounter + 1
		for p in range(0, len(self.instrList)):
			if(self.instrList[p].varType == "TEMP"):
				isFound = 0
				for i in range(0, len(self.tempTable)):
					if(self.tempTable[i].string == self.instrList[p].operand):
						self.instrList[p].operand = self.tempTable[i].value
						isFound = 1
				if isFound == 0:
					self.tempTable.append(TableEntry(self.instrList[p].operand, memCounter))
					self.instrList[p].operand = memCounter
					if(self.instrList[p].func == "LD"):
						self.instrList[p].func = "LDA"
					if(self.instrList[p].func == "ST"):
						self.instrList[p].func = "STA"
					memCounter = memCounter  + 1

		for p in range(0, len(self.instrList)):
			if(self.instrList[p].func == "LBL" and self.instrList[p].varType == "LABEL"):
				isFound = 0
				for i in range(0, len(self.labelTable)):
					if(self.labelTable[i].string == self.instrList[p].operand):
						self.instrList[p].operand = self.labelTable[i].value
						isFound = 1
				if isFound == 0:
					self.labelTable.append(TableEntry(self.instrList[p].operand, self.instrList[p].lineNum))
					self.instrList[p].operand = self.instrList[p].lineNum
					memCounter = memCounter + 1
				self.instrList[p].func = "NULL"

		for p in range(0, len(self.instrList)):
			if(self.instrList[p].func != "NULL" and self.instrList[p].varType == "LABEL"):
				for i in range(0, len(self.labelTable)):
					if(self.labelTable[i].string == self.instrList[p].operand):
						self.instrList[p].operand = self.labelTable[i].value 
class Expr :
	'''Virtual base class for expressions in the language'''

	def __init__( self ) :
		raise NotImplementedError(
			'Expr: pure virtual base class.  Do not instantiate' )

	def eval( self, nt, ft ) :
		'''Given an environment and a function table, evaluates the expression,
		returns the value of the expression (an int in this grammar)'''

		raise NotImplementedError(
			'Expr.eval: virtual method.  Must be overridden.' )

	def translate(self, nt, ri):

		raise NotImplementedError('Expr.translate: virtual method. Must be overrridden.')

	def display( self, nt, ft, depth=0 ) :
		'For debugging.'
		raise NotImplementedError(
			'Expr.display: virtual method.  Must be overridden.' )

class Number( Expr ) :
	'''Just integers'''

	def __init__( self, v=0 ) :
		self.value = v
	
	def eval( self, nt, ft ) :
		return self.value

	def translate(self, nt, ri) :
	
		con = ri.getNextConst(self.value)
		temp1 = ri.getNextTemp()
		ri.addInstr("LD", con, "CONST")
		ri.addInstr("ST", temp1, "TEMP")
		return temp1

	def display( self, nt, ft, depth=0 ) :
		print "%s%i" % (tabstop*depth, self.value)

class Ident( Expr ) :
	'''Stores the symbol'''

	def __init__( self, name ) :
		self.name = name
	
	def eval( self, nt, ft ) :
		return nt[ self.name ]

	def translate(self, nt, ri):
		temp1 = ri.getNextTemp()
		ri.addInstr("LD", self.name, "LOCAL")
		ri.addInstr("ST", temp1, "TEMP")
		return temp1

	def display( self, nt, ft, depth=0 ) :
		print "%s%s" % (tabstop*depth, self.name)


class Times( Expr ) :
	'''expression for binary multiplication'''

	def __init__( self, lhs, rhs ) :
		'''lhs, rhs are Expr's, the operands'''

		# test type here?
		# if type( lhs ) == type( Expr ) :
		self.lhs = lhs
		self.rhs = rhs
	
	def eval( self, nt, ft ) :
		return self.lhs.eval( nt, ft ) * self.rhs.eval( nt, ft )

	def translate(self, nt, ri):

		temp1 = self.lhs.translate(nt, ri)
		temp2 = self.rhs.translate(nt, ri)
		temp3 = ri.getNextTemp()
		ri.addInstr("LD", temp1, "TEMP")
		ri.addInstr("MUL", temp2, "TEMP")
		ri.addInstr("ST", temp3, "TEMP")
		return temp3

	def display( self, nt, ft, depth=0 ) :
		print "%sMULT" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Plus( Expr ) :
	'''expression for binary addition'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs
	
	def eval( self, nt, ft ) :
		return self.lhs.eval( nt, ft ) + self.rhs.eval( nt, ft )

	def translate(self, nt, ri):

		temp1 = self.lhs.translate(nt, ri)
		temp2 = self.rhs.translate(nt, ri)
		temp3 = ri.getNextTemp()
		ri.addInstr("LD", temp1, "TEMP")
		ri.addInstr("ADD", temp2, "TEMP")
		ri.addInstr("ST", temp3, "TEMP")
		return temp3	

	def display( self, nt, ft, depth=0 ) :
		print "%sADD" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Minus( Expr ) :
	'''expression for binary subtraction'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs
	
	def eval( self, nt, ft ) :
		return self.lhs.eval( nt, ft ) - self.rhs.eval( nt, ft )

	def translate(self, nt, ri):

		temp1 = self.lhs.translate(nt, ri)
		temp2 = self.rhs.translate(nt, ri)
		temp3 = ri.getNextTemp()
		ri.addInstr("LD", temp1, "TEMP")
		ri.addInstr("SUB", temp2, "TEMP")
		ri.addInstr("ST", temp3, "TEMP")
		return temp3

	def display( self, nt, ft, depth=0 ) :
		print "%sSUB" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


#-------------------------------------------------------

class Stmt :
	'''Virtual base class for statements in the language'''

	def __init__( self ) :
		raise NotImplementedError(
			'Stmt: pure virtual base class.  Do not instantiate' )

	def eval( self, nt, ft ) :
		'''Given an environment and a function table, evaluates the expression,
		returns the value of the expression (an int in this grammar)'''

		raise NotImplementedError(
			'Stmt.eval: virtual method.  Must be overridden.' )

	def translate(self, nt, ri):
		
		raise NotImplementedError('Stmt.translate: virtual method. Must be overridden')	

	def display( self, nt, ft, depth=0 ) :
		'For debugging.'
		raise NotImplementedError(
			'Stmt.display: virtual method.  Must be overridden.' )


class AssignStmt( Stmt ) :
	'''adds/modifies symbol in the current context'''

	def __init__( self, name, rhs ) :
		'''stores the symbol for the l-val, and the expressions which is the
		rhs'''
		self.name = name
		self.rhs = rhs
	
	def eval( self, nt, ft ) :
		nt[ self.name ] = self.rhs.eval( nt, ft )

	
	def translate(self, nt, ri):
		temp1 = self.rhs.translate( nt, ri)
		ri.addInstr("LD", temp1, "TEMP")
		ri.addInstr("ST", self.name, "LOCAL")

	def display( self, nt, ft, depth=0 ) :
		print "%sAssign: %s :=" % (tabstop*depth, self.name)
		self.rhs.display( nt, ft, depth+1 )


class IfStmt( Stmt ) :

	def __init__( self, cond, tBody, fBody ) :
		'''expects:
		cond - expression (integer)
		tBody - StmtList
		fBody - StmtList'''
		
		self.cond = cond
		self.tBody = tBody
		self.fBody = fBody

	def eval( self, nt, ft ) :
		if self.cond.eval( nt, ft ) > 0 :
			self.tBody.eval( nt, ft )
		else :
			self.fBody.eval( nt, ft )

	def translate(self, nt, ri):
		temp1 = self.cond.translate(nt,ri)
		label1 = ri.getNextLabel()
		label2 = ri.getNextLabel()
		ri.addInstr("LD", temp1, "TEMP")
		ri.addInstr("JMN", label1, "LABEL")
		ri.addInstr("JNZ", label1, "LABEL")
		self.tBody.translate(nt, ri)
		ri.addInstr("JMP", label2, "LABEL")
		ri.addLabel(label1)
		self.fBody.translate(nt, ri)
		ri.addLabel(label2)

	def display( self, nt, ft, depth=0 ) :
		print "%sIF" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sTHEN" % (tabstop*depth)
		self.tBody.display( nt, ft, depth+1 )
		print "%sELSE" % (tabstop*depth)
		self.fBody.display( nt, ft, depth+1 )


class WhileStmt( Stmt ) :

	def __init__( self, cond, body ) :
		self.cond = cond
		self.body = body

	def eval( self, nt, ft ) :
		while self.cond.eval( nt, ft ) > 0 :
			self.body.eval( nt, ft )

	def translate( self, nt, ri):
		label1 = ri.getNextLabel()
		label2 = ri.getNextLabel()
		ri.addLabel(label1)
		temp1 = self.cond.translate(nt,ri)
		ri.addInstr("LD", temp1, "TEMP")
		ri.addInstr("JMN", label2, "LABEL")
		ri.addInstr("JMZ", label2, "LABEL")
		self.body.translate(nt, ri)
		ri.addInstr("JMP", label1, "LABEL")
		ri.addLabel(label2) 

	def display( self, nt, ft, depth=0 ) :
		print "%sWHILE" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sDO" % (tabstop*depth)
		self.body.display( nt, ft, depth+1 )

#-------------------------------------------------------

class StmtList :
	'''builds/stores a list of Stmts'''

	def __init__( self ) :
		self.sl = []
	
	def insert( self, stmt ) :
		self.sl.insert( 0, stmt )
	
	def eval( self, nt, ft ) :
		for s in self.sl :
			s.eval( nt, ft )
	
	def translate(self, nt, ri):
		for s in self.sl :
			s.translate(nt, ri)	
		#TODO: IS THIS THE BEST PLACE TO DO THIS?
		for sIndex in range(len(ri.instrList)):
			if ri.instrList[sIndex].func == 'ST':
				ri.instrList[sIndex].func = 'STA'
			if ri.instrList[sIndex].func == 'LD':
				ri.instrList[sIndex].func = 'LDA'

	def optimize(self,ri):
#		toRemove = []
#		for sIndex in range(len(ri.instrList)-1):
			#IF sIndex is STORE N, and sIndex is LOAD N, add the load to the Remove list
#			if ri.instrList[sIndex].func.find('ST') != -1 and ri.instrList[sIndex+1].func.find('LD') != -1 and ri.instrList[sIndex].operand==ri.instrList[sIndex+1].operand:
#				toRemove.append(sIndex+1)
#		while len(toRemove) > 0:
#			ri.instrList.pop(toRemove.pop())#Removing in reverse order leaves earlier indexes unchanged
		m = 1
		for p in range(0, len(ri.instrList)):
			if(ri.instrList[p].func == "STA"):
				op = ri.instrList[p].operand
                                if(ri.instrList[m].func == "LDA" and ri.instrList[m].operand == op):
					ri.instrList[m].func = "NULL"
			m = m + 1
		line = 1
		for p in range(0, len(ri.instrList)):
			if(ri.instrList[p].func != "NULL"):
				ri.instrList[p].lineNum = line
				if(ri.instrList[p].func != "LBL"):
					line = line + 1

	def display( self, nt, ft, depth=0 ) :
		print "%sSTMT LIST" % (tabstop*depth)
		for s in self.sl :
			s.display( nt, ft, depth+1 )

class Program :
	
	def __init__( self, stmtList ) :
		self.stmtList = stmtList
		self.nameTable = {}
		self.funcTable = {}
		self.RAMinfo = RAMInfo()
	
	def eval( self ) :
		self.stmtList.eval( self.nameTable, self.funcTable )
	
	def translate(self) :
		self.stmtList.translate(self.nameTable, self.RAMinfo)
		self.RAMinfo.addInstr("HLT", "", "UNDEF")	

	def optimize(self):
		self.stmtList.optimize(self.RAMinfo)#Don't need nametable?

	def dump( self ) :
		print "Dump of Symbol Table"
		print "Name Table"
		for k in self.nameTable :
			print "  %s -> %s " % ( str(k), str(self.nameTable[k]) )
		print "Function Table"
		for k in self.funcTable :
			print "  %s" % str(k)

	def display( self, depth=0 ) :
		print "%sPROGRAM :" % (tabstop*depth)
		self.stmtList.display( self.nameTable, self.funcTable )

